Non-deterministic Turing machines

Generalizing rules from page 888 by making each right-hand side a list of possible outcomes, the list of configurations that can be reached after t steps is given by

NTMEvolve[rule_, inits_, t_Integer] := Nest[Union[Flatten[Map[NTMStep[rule, #]&, #], 1]]&, inits, t]

NTMStep[rule_List, {s_, a_, n_}] /; 1 ≤ n ≤ Length[a] := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a〚n〛}, rule], {1}]